package jm.data.structure.linked;

/**
 * @Description 单向循环链表实现
 * @date 2022/4/6 15:04
 */
public class CircleLinkedList<E> {
    /**
     * 链表长度
     */
    private int size;

    /**
     * 头节点
     */
    private Node<E> first;

    private static final int ELEMENT_NOT_FOUND = -1;

    private static class Node<E>{
        E element;
        Node<E> next;

        public Node(E element){
            this.element = element;
        }

        public Node(E element, Node<E> next){
            this.element = element;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }

    /**
     * 获取链表长度
     * @return
     */
    public int size(){
        return size;
    }

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty(){
        return size == 0;
    }

    /**
     * 清空链表
     */
    public void clean(){
        size = 0;
        first = null;
    }

    /**
     * 添加元素到index位置
     * @param index 位置
     * @param e 元素
     */
    public void add(int index, E e){
        rangeCheckForAdd(index);
        if (index == 0){
            Node<E> newFirst = new Node<E>(e,first);

            // 找到最后一个节点
            Node<E> nodeLast = (size == 0) ? newFirst :node(size - 1);
            nodeLast.next = newFirst;
            first = newFirst;
        }else {
            Node<E> prev = node(index - 1);
            prev.next = new Node<E>(e,prev.next);
        }
        size++;
    }

    /**
     * 添加元素到链表尾部
     * @param e
     */
    public void add(E e){
        add(size,e);
    }

    /**
     * 删除index位置的节点
     * @param index
     * @return
     */
    public E remove(int index){
        rangeCheck(index);
        Node<E> node = first;
        if (index == 0){
            if (size == 1){
                first = null;
            }else {
                Node<E> nodeLast = node(size - 1);
                first = first.next;
                nodeLast.next = first;
            }
        }else {
            Node<E> prev = node(index - 1);
            node = prev.next;
            prev.next = node.next;
        }
        size--;
        return node.element;
    }


    /**
     * 给index位置设置新的值
     * @param index
     * @param e
     * @return
     */
    public E set(int index, E e){
        Node<E> node = node(index);
        E oldE = node.element;
        node.element = e;
        return oldE;
    }

    /**
     * 返回index位置的元素
     * @param index
     * @return
     */
    public E get(int index){
        return node(index).element;
    }

    /**
     * 返回 元素 e 的位置
     * @param e
     * @return
     */
    public int indexOf(E e){
        Node<E> node = first;
        if (e == null){
            for (int i = 0; i < size; i++) {
                if (node.element == null){
                    return i;
                }
                node = node.next;
            }
        }else {
            for (int i = 0; i < size; i++) {
                if (e.equals(node.element)){
                    return i;
                }
                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 判断是否存在该元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        return indexOf(e) != ELEMENT_NOT_FOUND;
    }

    /**
     * 返回index位置的节点
     * @param index
     * @return
     */
    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    /**
     * 抛出异常方法
     * @param index
     */
    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /**
     * index限制
     * @param index
     */
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    /**
     * 添加时针对index限制
     * @param index
     */
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("LinkedList{list = [");
        Node<E> node = first;
        int i = 0;
        while (i < size){
            stringBuilder.append(node.element);
            if (i != size - 1){
                stringBuilder.append(",");
            }
            node = node.next;
            i++;
        }
        stringBuilder.append("]").append(",size = ").append(size).append("}");
        return stringBuilder.toString();
    }
}
